package 热题100;

import java.util.Scanner;

public class 热题32最长有效括号 {


    public static void main(String[] args) {
        热题32最长有效括号 o = new 热题32最长有效括号();
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            System.out.println(o.longestValidParentheses(sc.next()));
        }

    }

    /**
     * 使用三指针定位一个节点，从i - 1 ，i  和 i，i+1为中心位置，开始遍历，返回最大值
     * @param s
     * @return
     */
    public int longestValidParentheses(String s) {

        if(s.length() == 0 || s == null){
            return 0;
        }

        //状态容器
        int[] dp = new int[s.length()+1];

        //basecase : 第一个无论是（）那个，都是0
        for (int i = 1; i < s.length(); i++) {
            //如果是（，设置为0
            if (s.charAt(i) == '('){
//                dp[i+1] = 0;
            } else {//否则为），
                //判断他的前一位是否是（，是设置为2
                if (s.charAt(i-1) == '('){
                    dp[i+1] = dp[i-1] + 2;
                }else {//如果不是，判断i-dp[i]得位置得前一个位置是否是（，如果是，设置为i-dp[i-1] - 1 + dp[i-1] + 2
                    if (i - dp[i] - 1 >= 0){
                        if (s.charAt(i - dp[i] - 1) == '('){
                            dp[i+1] = dp[i - dp[i] - 1] + dp[i] + 2;
                        }
                    }
                }
            }
        }

        int max = 0;
        for (int i = 0; i < dp.length; i++) {
            max = max > dp[i] ? max : dp[i];
        }

        return max;
    }

}

